The present invention is directed to image processing and in particular to image scaling. As will be appreciated, scaling of an image is a fundamental element of an image processing system, be it a dedicated image processing system or one that is part of a digital printer, facsimile machine, or multifunctional device. The present invention is directed to a high speed method and apparatus for accomplishing one or two dimensional scaling of digitized images that are represented in a run length encoded manner.
Heretofore, a number of patents and publications have disclosed methods for image scaling, the relevant portions of which may be briefly summarized as follows:
R. Tuhro described in the Xerox Disclosure Journal, Vol. 5, No. 6, November/December 1980 (p. 639) Image Scaling Using Bit Throw-away Memory. In the disclosure, a logic circuit for accomplishing the scaling at a high data rate is taught.
U.S. Pat. No. 5,303,334 to Snyder et al., issued Apr. 12, 1994, teaches a system for rendering a graphic image. In particular, the system employs opcodes, wherein the opcodes are described as representing instructions to scale a source image and rotate a source image.
U.S. Pat. No. 5,245,441 to Ruben, issued Sep. 14, 1993, and incorporated by reference for its teachings related to CCITT compression, discloses an image processing method and apparatus, where an image stream is represented logically as a series of run length codes. During a decompression operation, CCITT encoded data is received, decoded into a full raster image, and clipping, windowing and scaling operations are then applied. At col. 8, lines 43-54, Ruben teaches the use of codes representing pixels of the same color and the performance of mathematical operations on such codes without converting them back into run lengths.
U.S. Pat. No. 5,113,494 to Menendez et al., issued May 12, 1992, appears to disclose a pipelined raster image processor. In the preferred embodiment, Menendez et al. describes a raster image processor (RIP) capable of performing several different image processing operations. The RIP contains a scaler, which receives output from a decompressor, for scaling the decompressed image from one resolution to another. The scaler is connected to a bus by which the image data is transferred on a block-by-block basis.
U.S. Pat. No. 5,239,625 to Bogart et al., issued Aug. 24, 1993, teaches the merging of images, particularly images represented in compressed format using run length encoding techniques. To accomplish scaling, the low resolution rasterization is multiplied by repeat pixel counts reflected in the run length data for a single raster line and identical lines are represented with repeat line counts.
In accordance with the present invention, there is provided a method, operating on a programmable data processing system, for scaling an image represented as a run length encoded data stream to produce a scaled run length encoded data stream representing a scaled version of the image, comprising the steps of: parsing the run length encoded data stream to determine the lengths of continuous runs of a color; multiplying each of the lengths by a scaling factor to produce a stream of scaled run lengths; applying at least one scaling rule to the stream of scaled run lengths to alter a run length therein; and outputting the scaled run lengths as a scaled run length encoded data stream.
In accordance with another aspect of the present invention, there is provided a method, operating on a programmable data processing system, for processing an image represented as a run length encoded data stream to produce a second run length encoded data stream representing a processed version of the image, comprising the steps of: parsing the run length encoded data stream to determine the lengths of continuous runs of a color; multiplying each of the lengths by a scaling factor to produce a stream of scaled run lengths; applying at least one scaling rule to the stream of scaled run lengths to alter a run length therein; and rotating the scaled run length encoded data stream while decoding the run length encoded data stream to produce a binary array of image signals, said binary array of image signals representing the image at a different resolution and orientation.
In accordance with yet another aspect of the present invention, there is provided an apparatus for scaling a run length encoded data stream, comprising: an input buffer for storing at least a portion of the run length encoded data stream; means for parsing the run length encoded data stream to determine the lengths of continuous runs of a color; arithmetic circuitry for multiplying each of the lengths by a scaling factor to produce a stream of scaled run lengths; and memory for storing the scaled run lengths as a scaled run length encoded data stream.
One aspect of the present invention deals with a basic problem in image processing, the fast scaling of image bitmaps. Resolution of this problem finds practical application in various image output devices where an image generated at a first resolution is constrained to be printed at a second resolution. For example, an image may be generated or scanned in at 300 dots per inch (dpi) but printed using an a print engine capable of rending marks on a substrate at 600 dpi. Alternatively, one may wish to print an image in a magnified or reduced fashion.
This aspect is further based on the discovery of a technique that alleviates this problem of different resolutions. The technique employs the compressed form of an image, when it has been represented as a run length encoded bit stream, to accomplish the scaling or resolution conversion in a computationally efficient manner. In particular, the preferred embodiment of the invention relies upon a fast scaling technique operating on run length encoded data to facilitate the rapid scaling during decoding of the run length data.
This technique can be implemented, for example, by any image processing system, be it hardware or software based. Machines implementing the invention may include printers, scanners, facsimile machines as well as multifunction machines. The hardware required preferably includes a microprocessor or similar control circuitry to control memory access (e.g., read/write) and to perform simple arithmetic operations on the stored data.
The technique described above is advantageous because it is not only simple but efficient. Furthermore, it can be adapted to any image processing system in which run length encoded data is generated or employed, making it available for use in any of a number of digital image processing systems, particularly those using run length encoding for data compression. The techniques of the invention are advantageous because they permit the highly efficient scaling of image bitmaps. The present invention is one of a plurality of image processing operations that can be applied to compressed image formats to enable faster processing of image data in an image processing system. Some of the related techniques can be used to perform image processing while decoding a run length encoded image. Other techniques include the scaling of an image while decoding.